package leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/14 20:59
 * @描述 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */

public class Solution0234 {


    /**
     * 转换为数组之后再判断
     *
     * @param head
     * @return
     */
    public static boolean solutionNums(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        List<Integer> li = new ArrayList<>();
        while (head.next != null) {
            li.add(head.val);
            head = head.next;
        }
        int left = 0, right = li.size() - 1;
        while (left < right) {
            if (!Objects.equals(li.get(left), li.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * 快慢指针解法， 中点之后部分反转与前部比较
     *
     * @param head
     * @return
     */
    public static boolean solutionQuickSlow(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        if (fast != null) {
            slow = slow.next;
        }
        while (pre != null && slow != null) {
            if (pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}


